#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

struct Treenode
{
	int val;
	struct Treenode* left, *right;
	Treenode() :val(0), left(nullptr), right(nullptr){}
	Treenode(int val):val(val),left(nullptr),right(nullptr){}
	Treenode(int val, Treenode* left, Treenode* rigth):val(val), left(left), right(right) {}
};

vector<vector<int>> res;
vector<int> ans;
vector<vector<int>> bfs(Treenode* root)
{
	queue<Treenode*> q;
	q.push(root);
	while (!q.empty())
	{
		int num = q.size();
		for (int i = 0;i < num;i++)
		{
			auto t = q.front();
			q.pop();
			ans.push_back(t->val);
			if (t->left) q.push(t->left);
			if (t->right) q.push(t->right);
		}
		res.push_back(ans);
		ans.clear();
	}
	return res;
}

int main()
{
	Treenode* root = new Treenode(3);
	root->left = new Treenode(9);
	root->right = new Treenode(20);
	root->right->left = new Treenode(15);
	root->right->right = new Treenode(7);
	bfs(root);
	for (int i = 0;i < res.size();i++)
	{
		if (i % 2 == 1) reverse(res[i].begin(), res[i].end());
	}
	for (int i = 0;i < res.size();i++)
	{
		for (int j = 0;j < res[i].size();j++)
		{
			cout << res[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}